//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 
//
// 示例 1: 
//
// 输入: "abcabcbb"
//输出: 3 
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 
//
// 示例 2: 
//
// 输入: "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
// 
//
// 示例 3: 
//
// 输入: "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
// 
// Related Topics 哈希表 双指针 字符串 Sliding Window


package com.yun.leetcode.editor.cn;

public class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new LongestSubstringWithoutRepeatingCharacters().new Solution();
        System.err.println(solution.lengthOfLongestSubstring("aabaab!bb"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            int left = 0;
            int right = 0;
            int maxLength = 0;
            boolean[] flag = new boolean[256];
            int len = s.length();
            for (int i = 0; i < len; i++) {
                char c = s.charAt(i);
                if (!flag[c]) {
                    right++;
                    flag[c] = true;
                }else{
                    // 已经包含了，移动左指针
                    // 以下是错误的，考虑太少，这么直接把所有的位置都清掉了
                   /* while (flag[s.charAt(left)]) {
                        flag[s.charAt(left)] = false;
                        left++;
                    }*/

                    while (left <= right) {
                        if (s.charAt(left) == c) {
                            left++;
                            break;
                        }
                        //	测试用例:"axdxdddewxfd" 测试结果:3 期望结果:5
                        // 中间序列已经包含的窗格，肯定都是只包含一次的，现在要跳到出现跟目标字符相同的后一个位置
                        flag[s.charAt(left)] = false;
                        left++;
                    }
                    right ++;
                }
                maxLength = Math.max(right - left, maxLength);
            }
            return maxLength;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}